<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>BST</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="bst">BST</h1>
<h1 id="1-lc-705-design-hashset">1. LC 705. Design HashSet</h1>
<ul>
<li><a href="https://leetcode.com/problems/design-hashset/">https://leetcode.com/problems/design-hashset/</a></li>
</ul>
<p>链表法 + BST 来实现hashset</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MyHashSet</span>:</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        <span class="hljs-string">"""
        Initialize your data structure here.
        """</span>
        self.keyRange = <span class="hljs-number">769</span>
        self.bucketArray = [Bucket() <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(self.keyRange)]

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_hash</span><span class="hljs-params">(self, key)</span> -&gt; int:</span>
        <span class="hljs-keyword">return</span> key % self.keyRange

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">add</span><span class="hljs-params">(self, key: int)</span> -&gt; <span class="hljs-keyword">None</span>:</span>
        bucketIndex = self._hash(key)
        self.bucketArray[bucketIndex].insert(key)

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">remove</span><span class="hljs-params">(self, key: int)</span> -&gt; <span class="hljs-keyword">None</span>:</span>
        <span class="hljs-string">"""
        :type key: int
        :rtype: None
        """</span>
        bucketIndex = self._hash(key)
        self.bucketArray[bucketIndex].delete(key)

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">contains</span><span class="hljs-params">(self, key: int)</span> -&gt; bool:</span>
        <span class="hljs-string">"""
        Returns true if this set contains the specified element
        :type key: int
        :rtype: bool
        """</span>
        bucketIndex = self._hash(key)
        <span class="hljs-keyword">return</span> self.bucketArray[bucketIndex].exists(key)

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Bucket</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        self.tree = BSTree()

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insert</span><span class="hljs-params">(self, value)</span>:</span>
        self.tree.root = self.tree.insertIntoBST(self.tree.root, value)

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">delete</span><span class="hljs-params">(self, value)</span>:</span>
        self.tree.root = self.tree.deleteNode(self.tree.root, value)

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">exists</span><span class="hljs-params">(self, value)</span>:</span>
        <span class="hljs-keyword">return</span> (self.tree.searchBST(self.tree.root, value) <span class="hljs-keyword">is</span> <span class="hljs-keyword">not</span> <span class="hljs-literal">None</span>)

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">TreeNode</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, value)</span>:</span>
        self.val = value
        self.left = <span class="hljs-literal">None</span>
        self.right = <span class="hljs-literal">None</span>

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">BSTree</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self)</span>:</span>
        self.root = <span class="hljs-literal">None</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">searchBST</span><span class="hljs-params">(self, root: TreeNode, val: int)</span> -&gt; TreeNode:</span>
        <span class="hljs-keyword">if</span> root <span class="hljs-keyword">is</span> <span class="hljs-literal">None</span> <span class="hljs-keyword">or</span> val == root.val:
            <span class="hljs-keyword">return</span> root

        <span class="hljs-keyword">return</span> self.searchBST(root.left, val) <span class="hljs-keyword">if</span> val &lt; root.val \
            <span class="hljs-keyword">else</span> self.searchBST(root.right, val)

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">insertIntoBST</span><span class="hljs-params">(self, root: TreeNode, val: int)</span> -&gt; TreeNode:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root:
            <span class="hljs-keyword">return</span> TreeNode(val)

        <span class="hljs-keyword">if</span> val &gt; root.val:
            <span class="hljs-comment"># insert into the right subtree</span>
            root.right = self.insertIntoBST(root.right, val)
        <span class="hljs-keyword">elif</span> val == root.val:
            <span class="hljs-keyword">return</span> root
        <span class="hljs-keyword">else</span>:
            <span class="hljs-comment"># insert into the left subtree</span>
            root.left = self.insertIntoBST(root.left, val)
        <span class="hljs-keyword">return</span> root

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">successor</span><span class="hljs-params">(self, root)</span>:</span>
        <span class="hljs-string">"""
        One step right and then always left
        """</span>
        root = root.right
        <span class="hljs-keyword">while</span> root.left:
            root = root.left
        <span class="hljs-keyword">return</span> root.val

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">predecessor</span><span class="hljs-params">(self, root)</span>:</span>
        <span class="hljs-string">"""
        One step left and then always right
        """</span>
        root = root.left
        <span class="hljs-keyword">while</span> root.right:
            root = root.right
        <span class="hljs-keyword">return</span> root.val

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">deleteNode</span><span class="hljs-params">(self, root: TreeNode, key: int)</span> -&gt; TreeNode:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> root:
            <span class="hljs-keyword">return</span> <span class="hljs-literal">None</span>

        <span class="hljs-comment"># delete from the right subtree</span>
        <span class="hljs-keyword">if</span> key &gt; root.val:
            root.right = self.deleteNode(root.right, key)
        <span class="hljs-comment"># delete from the left subtree</span>
        <span class="hljs-keyword">elif</span> key &lt; root.val:
            root.left = self.deleteNode(root.left, key)
        <span class="hljs-comment"># delete the current node</span>
        <span class="hljs-keyword">else</span>:
            <span class="hljs-comment"># the node is a leaf</span>
            <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> (root.left <span class="hljs-keyword">or</span> root.right):
                root = <span class="hljs-literal">None</span>
            <span class="hljs-comment"># the node is not a leaf and has a right child</span>
            <span class="hljs-keyword">elif</span> root.right:
                root.val = self.successor(root)
                root.right = self.deleteNode(root.right, root.val)
            <span class="hljs-comment"># the node is not a leaf, has no right child, and has a left child</span>
            <span class="hljs-keyword">else</span>:
                root.val = self.predecessor(root)
                root.left = self.deleteNode(root.left, root.val)

        <span class="hljs-keyword">return</span> root

<span class="hljs-comment"># Your MyHashSet object will be instantiated and called as such:</span>
<span class="hljs-comment"># obj = MyHashSet()</span>
<span class="hljs-comment"># obj.add(key)</span>
<span class="hljs-comment"># obj.remove(key)</span>
<span class="hljs-comment"># param_3 = obj.contains(key)</span>
</div></code></pre>
<h1 id="2-article-700-search-in-a-bst">2. Article 700. Search in a BST</h1>
<ul>
<li><a href="https://leetcode.com/problems/search-in-a-binary-search-tree/">https://leetcode.com/problems/search-in-a-binary-search-tree/</a></li>
</ul>
<h1 id="3-article-701-insert-in-a-bst">3. Article 701. Insert in a BST</h1>
<ul>
<li><a href="https://leetcode.com/problems/insert-into-a-binary-search-tree/">https://leetcode.com/problems/insert-into-a-binary-search-tree/</a></li>
</ul>
<h1 id="4-article-450-delete-in-a-bst">4. Article 450. Delete in a BST</h1>
<ul>
<li><a href="https://leetcode.com/problems/delete-node-in-a-bst/">https://leetcode.com/problems/delete-node-in-a-bst/</a></li>
</ul>
<h1 id="5-270-closest-binary-search-tree-value">5. 270. Closest Binary Search Tree Value</h1>
<ul>
<li><a href="https://leetcode.com/problems/closest-binary-search-tree-value/">https://leetcode.com/problems/closest-binary-search-tree-value/</a></li>
</ul>
<p>在给定的二叉搜索树里面查找和target最接近的value</p>
<p>官方解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">closestValue</span><span class="hljs-params">(self, root: TreeNode, target: float)</span> -&gt; int:</span>
        closest = root.val
        <span class="hljs-keyword">while</span> root:
            closest = min(root.val, closest, key = <span class="hljs-keyword">lambda</span> x: abs(target - x))
            root = root.left <span class="hljs-keyword">if</span> target &lt; root.val <span class="hljs-keyword">else</span> root.right
        <span class="hljs-keyword">return</span> closest
</div></code></pre>
<p>我的解法, 找到 floor(target) 和ceil(target), 再比较一下</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">closestValue</span><span class="hljs-params">(self, root: TreeNode, target: float)</span> -&gt; int:</span>
        
        self.pre1 = <span class="hljs-literal">None</span>
        self.post1 = <span class="hljs-literal">None</span>
        self.last = <span class="hljs-literal">None</span>
        self.travel(root, target)
        <span class="hljs-keyword">if</span> self.pre1 == <span class="hljs-literal">None</span>:
            self.pre1 = self.last
        <span class="hljs-keyword">if</span> self.post1 == <span class="hljs-literal">None</span>:
            self.post1 = self.last
        <span class="hljs-keyword">if</span> abs(self.pre1.val - target) &lt;= abs(self.post1.val - target):
            <span class="hljs-keyword">return</span> self.pre1.val
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> self.post1.val
        
        
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">travel</span><span class="hljs-params">(self, node, target)</span>:</span>
        <span class="hljs-keyword">if</span> node == <span class="hljs-literal">None</span>:
            <span class="hljs-keyword">return</span> 
        <span class="hljs-keyword">if</span> node.val &lt;= target:
            self.pre1 = node
        <span class="hljs-keyword">if</span> node.val &gt;= target:
            self.post1 = node
        self.last = node
        <span class="hljs-keyword">if</span> node.val &gt; target:
            self.travel(node.left, target)
        <span class="hljs-keyword">if</span> node.val &lt; target:
            self.travel(node.right, target)
</div></code></pre>

    </body>
    </html>